<?php
/**
 * Created by PhpStorm.
 * User: Administrator
 * Date: 2020/4/2 0002
 * Time: 15:09
 */

class QuestionCombination
{
    /**
     * @param $data  array 题目信息
     * @param $sum  int 卷总分
     * @param $weights  array map 权重映射
     * @return array|bool
     */
    public static function select($data,$sum,$weights){
        $weightMap = [];    // 获得每个分数题目的权重映射
        $scoreSum = 0;  // 所有题目加起来总分数
        $scoreArr = []; // 所有分数单个存数组
        foreach ($data as $dv){
            if(!isset($weightMap[$dv['score']])){
                $weightMap[$dv['score']] = [
//                    'weights'=>0,   // 总权重
                    'cnt'=>0,       // 总题数
                ];
            }
//            $weightMap[$dv['score']]['weights']+=$dv['weights'];

            $weightMap[$dv['score']]['cnt']++;
            $scoreSum+=$dv['score'];
            $scoreArr[] = $dv['score'];
        }
        if($scoreSum <= $sum){  // 题目总分达不到卷总分，直接把所有题目输出
            return $data;
        }
        $arr = self::weightMap2Arr($weightMap);
        $availableCombinations = self::checkValid($arr,$sum);
        $combination = self::combinationFilter($availableCombinations,$weights);    // 此处获得分数配比  后续可接各属性  如难度等等
        return self::getRandQuestion($data,$combination['combination']);
    }


    /**
     * 检查是否最终组合能得到总数
     * @param $weightArr
     * @param $sum
     * @param int $current 当前总数
     * @param array $currentArr 当前组合
     * @param array $allCombination 存所有可能的组合
     * @return bool
     */
    public static function checkValid($weightArr,$sum,$current=0,$currentArr=[],$allCombination=[]){
        $arr = array_pop($weightArr);
        $ca = $currentArr;
        for ($i = 0;$i<=$arr['cnt'];$i++){
            $currentSum= $current+$arr['score']*$i;
            if($i >0){
                $ca[] = $arr['score'];
            }
            if($currentSum == $sum){
                $allCombination[] = $ca;
                continue;
            }
            if(sizeof($weightArr) > 0){
                $allCombination = self::checkValid($weightArr,$sum,$currentSum,$ca,$allCombination);
            }
        }
        return $allCombination;
    }

    /**
     * 将分数=>属性转成全属性
     * @param $weightMap
     * @return array
     */
    public static function weightMap2Arr($weightMap){
        $arr = [];
        foreach ($weightMap as $k=>&$v){
            $arr[] = array_merge([
                'score'=>$k
            ],$v);
        }
        return $arr;
    }

     /**
     * 获取组合平均差
     * 平均差不适合此处已改为基于权重的随机距离
     * @param $combination array 组合
     * @param $weights array 权重数组
     * @return float|int
     */
    public static function combinationDistance($combination,$weights){
        return self::randDistance($combination,$weights);

        $scoreCountMap = [];
        $cnt = sizeof($combination);
        foreach ($combination as $v){ // 从平均差算适配
            if(!isset($scoreCountMap[$v])){
                $scoreCountMap[$v] = 0;
            }
            $scoreCountMap[$v]++;
        }
        $weightsSum = array_sum($weights);
        foreach ($weights as $wk=>&$wv){
            $wv = round($wv/$weightsSum,2);
        }

        $distance = 0;
        foreach ($combination as $ck=>$cv){
            $rate = round($cv/$cnt,2);
            $distance+= abs($rate - $weights[$cv]);
        }
        return $distance;
    }

    /**
     * 获取随机分
     * @param $weights
     * @return int|string
     */
    public static function getRandScore($weights)
    {
        $weightsSum = array_sum($weights);
        if($weightsSum == 0){   // 未设置权重，则所有分数权重平均
            $scores = array_keys($weights);
            return $scores[mt_rand(0,sizeof($scores) - 1)];
        }
        $randNum = mt_rand(1,$weightsSum);
        $i = 0;
        foreach ($weights as $k=>$v){
            if($randNum > $i && $randNum <= $i+$v){
                return  $k;
            }
            $i+=$v;
        }
        return -1;
    }

    /**
     * 依据权重获取随机距离
     * @param $combination
     * @param $weights
     * @return float|int
     */
    public static function randDistance($combination,$weights)
    {
        $distance = 0;
        foreach ($combination as $v){
            $randScore = self::getRandScore($weights);
            if($randScore == $v){
                $distance+=0;
            }else{
                $distance+=1;
            }
        }
        return $distance/sizeof($combination);  // 因为题目个数并不确定，所以除以数量
    }

    /**
     * 筛选所有组合选出最小平均差的组合   也就是最优组合
     * @param $availableCombinations
     * @param $weights
     * @return array
     */
    public static function combinationFilter($availableCombinations,$weights){
        $minDistance = 0;   // 最小平均差
        $key = 0;   // 最小平均差的key
        foreach ($availableCombinations as $k=>$v){
            $distance = self::combinationDistance($v,$weights);
            if($k == 0){
                $minDistance = $distance;
                $key = $k;
                continue;
            }
            if($minDistance > $distance){
                $minDistance = $distance;
                $key = $k;
            }
        }
        return [
            'combination'=>$availableCombinations[$key],
            'fit'=>$minDistance
        ];
    }

    public static function getRandQuestion($data,$combination)
    {
        $scoreIdMap = [];
        foreach ($data as $k=>$v){
            if(!isset($scoreIdMap[$v['score']])){
                $scoreIdMap[$v['score']] = [];
            }
            $scoreIdMap[$v['score']][] = $k;
        }
        $result = [];

        foreach ($combination as $cv){
            shuffle($scoreIdMap[$cv]);
            $result[] = $data[array_pop($scoreIdMap[$cv])];
        }
        return $result;
    }
}